# encoding: utf-8

# Pretty-printers for Boost (http://www.boost.org)

# Copyright (C) 2009 Rüdiger Sonderfeld <ruediger@c-plusplus.de>

# Boost Software License - Version 1.0 - August 17th, 2003

# Permission is hereby granted, free of charge, to any person or organization
# obtaining a copy of the software and accompanying documentation covered by
# this license (the "Software") to use, reproduce, display, distribute,
# execute, and transmit the Software, and to prepare derivative works of the
# Software, and to permit third-parties to whom the Software is furnished to
# do so, all subject to the following:

# The copyright notices in the Software and this entire statement, including
# the above license grant, this restriction and the following disclaimer,
# must be included in all copies of the Software, in whole or in part, and
# all derivative works of the Software, unless such copies or derivative
# works are solely in the form of machine-executable object code generated by
# a source language processor.

# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
# SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
# FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
# ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
# DEALINGS IN THE SOFTWARE.

#
# Inspired _but not copied_ from libstdc++'s pretty printers
#

import datetime
import gdb
import re
import sys

_have_gdb_printing = True
try:
    import gdb.printing
except ImportError:
    _have_gdb_printing = False

try:
    from gdb.types import get_basic_type
except ImportError:
    # from libstdcxx printers
    def get_basic_type(type):
        # If it points to a reference, get the reference.
        if type.code == gdb.TYPE_CODE_REF:
            type = type.target()

        # Get the unqualified type, stripped of typedefs.
        type = type.unqualified().strip_typedefs()

        return type

from gdb import execute
_have_execute_to_string = True
try:
    s = execute('help', True, True)
    # detect how to invoke ptype
    ptype_cmd = 'ptype/mtr'
    try:
        gdb.execute(ptype_cmd + ' void', True, True)
    except RuntimeError:
        ptype_cmd = 'ptype'
except TypeError:
    _have_execute_to_string = False

try:
    from gdb import parse_and_eval
except ImportError:
    # from http://stackoverflow.com/a/2290941/717706
    def parse_and_eval(exp):
        if gdb.VERSION.startswith("6.8.50.2009"):
            return gdb.parse_and_eval(exp)
        # Work around non-existing gdb.parse_and_eval as in released 7.0
        gdb.execute("set logging redirect on")
        gdb.execute("set logging on")
        gdb.execute("print %s" % exp)
        gdb.execute("set logging off")
        return gdb.history(0)

try:
    class GDB_Value_Wrapper(gdb.Value):
        "Wrapper class for gdb.Value that allows setting extra properties."
        def __init__(self, value):
            super(GDB_Value_Wrapper, self).__init__(value)
            self.__dict__ = {}
except TypeError:
    class GDB_Value_Wrapper():
        "Wrapper class for gdb.Value that allows setting extra properties."
        def __init__(self, value):
            self.gdb_value = value
            self.__dict__ = {}
            self.__dict__['type'] = value.type
            self.__dict__['address'] = value.address
            self.__getitem__ = value.__getitem__


class Printer_Gen(object):

    class SubPrinter_Gen(object):
        def match_re(self, v):
            return self.re.search(str(v.basic_type)) != None

        def __init__(self, Printer):
            self.name = Printer.printer_name + '-' + Printer.version
            self.enabled = True
            if hasattr(Printer, 'supports'):
                self.re = None
                self.supports = Printer.supports
            else:
                self.re = re.compile(Printer.type_name_re)
                self.supports = self.match_re
            self.Printer = Printer

        def __call__(self, v):
            if not self.enabled:
                return None
            if self.supports(v):
                v.type_name = str(v.basic_type)
                return self.Printer(v)
            return None

    def __init__(self, name):
        self.name = name
        self.enabled = True
        self.subprinters = []

    def add(self, Printer):
        self.subprinters.append(Printer_Gen.SubPrinter_Gen(Printer))

    def __call__(self, value):
        v = GDB_Value_Wrapper(value)
        v.basic_type = get_basic_type(v.type)
        if not v.basic_type:
            return None
        if _is_boost_multi_index(v):
            if long(v.address) in Boost_Multi_Index.idx:
                v.idx = Boost_Multi_Index.idx[long(v.address)]
            else:
                v.idx = 0
        for subprinter_gen in self.subprinters:
            printer = subprinter_gen(v)
            if printer != None:
                return printer
        return None


printer_gen = Printer_Gen('boost')

# This function registers the top-level Printer generator with gdb.
# This should be called from .gdbinit.
def register_printer_gen(obj):
    "Register printer generator with objfile obj."

    global printer_gen

    if _have_gdb_printing:
        gdb.printing.register_pretty_printer(obj, printer_gen, replace=True)
    else:
        if obj is None:
            obj = gdb
        obj.pretty_printers.append(printer_gen)

# Register individual Printer with the top-level Printer generator.
def _register_printer(Printer):
    "Registers a Printer"
    printer_gen.add(Printer)
    return Printer

def _cant_register_printer(Printer):
    print >> sys.stderr, 'Printer [%s] not supported by this gdb version' % Printer.printer_name
    return Printer

def _conditionally_register_printer(condition):
    if condition:
        return _register_printer
    else:
        return _cant_register_printer

###
### Individual Printers follow.
###
### Relevant fields:
###
### - 'printer_name' : Subprinter name used by gdb. (Required.) If it contains
###     regex operators, they must be escaped when referring to it from gdb.
### - 'version' : Appended to the subprinter name. (Required.)
### - 'supports(GDB_Value_Wrapper)' classmethod : If it exists, it is used to
###     determine if the Printer supports the given object.
### - 'type_name_re' : If 'supports(basic_type)' doesn't exist, a default
###     version is used which simply tests whether the type name matches this
###     re. (Either supports() or type_name_re is required.)
### - '__init__' : Its only argument is a GDB_Value_Wrapper.
###

@_register_printer
class BoostIteratorRange:
    "Pretty Printer for boost::iterator_range (Boost.Range)"
    printer_name = 'boost::iterator_range'
    version = '1.40'
    type_name_re = '^boost::iterator_range<.*>$'

    class _iterator:
        def __init__(self, begin, end):
            self.item = begin
            self.end = end
            self.count = 0

        def __iter__(self):
            return self

        def next(self):
            if self.item == self.end:
                raise StopIteration
            count = self.count
            self.count = self.count + 1
            elem = self.item.dereference()
            self.item = self.item + 1
            return ('[%d]' % count, elem)

    def __init__(self, value):
        self.typename = value.type_name
        self.value = value

    def children(self):
        return self._iterator(self.value['m_Begin'], self.value['m_End'])

    def to_string(self):
        begin = self.value['m_Begin']
        end = self.value['m_End']
        return '%s of length %d' % (self.typename, int(end - begin))

    def display_hint(self):
        return 'array'

@_register_printer
class BoostOptional:
    "Pretty Printer for boost::optional (Boost.Optional)"
    printer_name = 'boost::optional'
    version = '1.40'
    type_name_re = '^boost::optional<(.*)>$'
    regex = re.compile(type_name_re)

    def __init__(self, value):
        self.typename = value.type_name
        self.value = value

    class _iterator:
        def __init__(self, member, empty):
            self.member = member
            self.done = empty

        def __iter__(self):
            return self

        def next(self):
            if(self.done):
                raise StopIteration
            self.done = True
            return ('value', self.member.dereference())

    def children(self):
        initialized = self.value['m_initialized']
        if(not initialized):
            return self._iterator('', True)
        else:
            match = BoostOptional.regex.search(self.typename)
            if match:
                try:
                    membertype = gdb.lookup_type(match.group(1)).pointer()
                    member = self.value['m_storage']['dummy_']['data'].address.cast(membertype)
                    return self._iterator(member, False)
                except:
                    return self._iterator('', True)

    def to_string(self):
        initialized = self.value['m_initialized']
        if(not initialized):
            return "%s is not initialized" % self.typename
        else:
            return "%s is initialized" % self.typename

@_register_printer
class BoostReferenceWrapper:
    "Pretty Printer for boost::reference_wrapper (Boost.Ref)"
    printer_name = 'boost::reference_wrapper'
    version = '1.40'
    type_name_re = '^boost::reference_wrapper<(.*)>$'

    def __init__(self, value):
        self.typename = value.type_name
        self.value = value

    def to_string(self):
        return '(%s) %s' % (self.typename, self.value['t_'].dereference())

@_register_printer
class BoostTribool:
    "Pretty Printer for boost::logic::tribool (Boost.Tribool)"
    printer_name = 'boost::logic::tribool'
    version = '1.40'
    type_name_re = '^boost::logic::tribool$'

    def __init__(self, value):
        self.typename = value.type_name
        self.value = value

    def to_string(self):
        state = self.value['value']
        s = 'indeterminate'
        if(state == 0):
            s = 'false'
        elif(state == 1):
            s = 'true'
        return '(%s) %s' % (self.typename, s)

@_register_printer
class BoostScopedPtr:
    "Pretty Printer for boost::scoped/intrusive_ptr/array (Boost.SmartPtr)"
    printer_name = 'boost::scoped/intrusive_ptr/array'
    version = '1.40'
    type_name_re = '^boost::(intrusive|scoped)_(ptr|array)<(.*)>$'

    def __init__(self, value):
        self.typename = value.type_name
        self.value = value

    def to_string(self):
        return '(%s) %s' % (self.typename, self.value['px'])

@_register_printer
class BoostSharedPtr:
    "Pretty Printer for boost::shared/weak_ptr/array (Boost.SmartPtr)"
    printer_name = 'boost::shared/weak_ptr/array'
    version = '1.40'
    type_name_re = '^boost::(weak|shared)_(ptr|array)<(.*)>$'

    def __init__(self, value):
        self.typename = value.type_name
        self.value = value

    def to_string(self):
        if self.value['px'] == 0x0:
            return '(%s) %s' % (self.typename, self.value['px'])
        countobj = self.value['pn']['pi_'].dereference()
        refcount = countobj['use_count_']
        weakcount = countobj['weak_count_']
        return '(%s) (count %d, weak count %d) %s' % (self.typename,
                                                      refcount, weakcount,
                                                      self.value['px'])

@_register_printer
class BoostCircular:
    "Pretty Printer for boost::circular_buffer (Boost.Circular)"
    printer_name = 'boost::circular_buffer'
    version = '1.40'
    type_name_re = '^boost::circular_buffer<(.*)>$'

    class _iterator:
        def __init__(self, first, last, buff, end, size):
            self.item = first # virtual beginning of the circular buffer
            self.last = last  # virtual end of the circular buffer (one behind the last element).
            self.buff = buff  # internal buffer used for storing elements in the circular buffer
            self.end = end    # internal buffer's end (end of the storage space).
            self.size = size
            self.capa = int(end-buff)
            self.count = 0

        def __iter__(self):
            return self

        def next(self):
            if self.count == self.size:
                raise StopIteration
            count = self.count
            crt=self.buff + (count + self.item - self.buff) % self.capa
            elem = crt.dereference()
            self.count = self.count + 1
            return ('[%d]' % count, elem)




            if self.item == self.last:
                raise StopIteration
            count = self.count
            self.count = self.count + 1
            elem = self.item.dereference()
            self.item = self.item + 1
            if self.item == self.end:
                self.item == self.buff
            return ('[%d]' % count, elem)

    def __init__(self, value):
        self.typename = value.type_name
        self.value = value

    def children(self):
        return self._iterator(self.value['m_first'], self.value['m_last'], self.value['m_buff'], self.value['m_end'], self.value['m_size'])

    def to_string(self):
        first = self.value['m_first']
        last = self.value['m_last']
        buff = self.value['m_buff']
        end = self.value['m_end']
        size = self.value['m_size']
        return '%s of length %d/%d' % (self.typename, int(size), int(end-buff))

    def display_hint(self):
        return 'array'

@_register_printer
class BoostArray:
    "Pretty Printer for boost::array (Boost.Array)"
    printer_name = 'boost::array'
    version = '1.40'
    type_name_re = '^boost::array<(.*)>$'

    def __init__(self, value):
        self.typename = value.type_name
        self.value = value

    def to_string(self):
        return self.value['elems']

    def display_hint(self):
        return 'array'

@_register_printer
class BoostVariant:
    "Pretty Printer for boost::variant (Boost.Variant)"
    printer_name = 'boost::variant'
    version = '1.40'
    type_name_re = '^boost::variant<(.*)>$'
    regex = re.compile(type_name_re)

    def __init__(self, value):
        self.typename = value.type_name
        self.value = value

    def to_string(self):
        m = BoostVariant.regex.search(self.typename)
        types = map(lambda s: s.strip(), re.split(r', (?=(?:<[^>]*?(?: [^>]*)*))|, (?=[^>,]+(?:,|$))', m.group(1)))
        which = long(self.value['which_'])
        type = types[which]
        data = ''
        try:
            ptrtype = gdb.lookup_type(type).pointer()
            data = self.value['storage_']['data_']['buf'].address.cast(ptrtype)
        except:
            data = self.value['storage_']['data_']['buf']
        return '(boost::variant<...>) which (%d) = %s value = %s' % (which,
                                                                     type,
                                                                     data.dereference())

@_register_printer
class BoostUuid:
    "Pretty Printer for boost::uuids::uuid (Boost.Uuid)"
    printer_name = 'boost::uuids::uuid'
    version = '1.40'
    type_name_re = '^boost::uuids::uuid$'

    def __init__(self, value):
        self.typename = value.type_name
        self.value = value

    def to_string(self):
        u = (self.value['data'][i] for i in xrange(16))
        s = 'xxxx-xx-xx-xx-xxxxxx'.replace('x', '%02x') % tuple(u)
        return '(%s) %s' % (self.typename, s)

##################################################
# boost::container::flat_set                     #
##################################################

@_register_printer
class BoostContainerFlatSet:
    "Pretty Printer for boost::container::flat_set (Boost.Container)"
    printer_name = 'boost::container::flat_set'
    version = '1.52'
    type_name_re = '^boost::container::flat_set<.*>$'

    class Iterator:
        def __init__(self, pointer, size):
            self.pointer = pointer
            self.size = size
            self.count = 0

        def __iter__(self):
            return self

        def next(self):
            if self.count == self.size:
                raise StopIteration

            count = self.count
            elt = self.pointer.dereference()
            self.pointer = self.pointer + 1
            self.count = self.count + 1
            return ('[%d]' % count, elt)

    def __init__(self, value):
        self.val = value
        self.element_type = self.val.type.strip_typedefs().template_argument(0)

    def get_pointer(self):
        return self.val["m_flat_tree"]["m_data"]["m_vect"]["members_"]["m_start"]

    def get_size(self):
        return self.val["m_flat_tree"]["m_data"]["m_vect"]["members_"]["m_size"]

    def get_capacity(self):
        return self.val["m_flat_tree"]["m_data"]["m_vect"]["members_"]["m_capacity"]

    def has_elements(self):
        if self.get_pointer():
            return True
        else:
            return False

    def to_string (self):
        if (self.has_elements()):
            return "boost::container::flat_set<%s> with %d elements, capacity %d" % (
                self.element_type, self.get_size(), self.get_capacity())
        else:
            return "empty boost::container::flat_set<%s>" % (self.element_type)

    def children (self):
        return self.Iterator(self.get_pointer(), self.get_size())

    def display_hint(self):
        return 'array'

##################################################
# boost::container::flat_map                     #
##################################################

@_register_printer
class BoostContainerFlatMap:
    "Pretty Printer for boost::container::flat_map (Boost.Container)"
    printer_name = 'boost::container::flat_map'
    version = '1.52'
    type_name_re = '^boost::container::flat_map<.*>$'

    class Iterator:
        def __init__(self, pointer, size):
            self.pointer = pointer
            self.size = size
            self.count = 0

        def __iter__(self):
            return self

        def next(self):
            if self.count == self.size * 2:
                raise StopIteration

            if self.count % 2 == 0:
                item = self.pointer.dereference()["first"]
            else:
                item = self.pointer.dereference()["second"]
                self.pointer = self.pointer + 1

            count = self.count
            self.count = self.count + 1
            return ('[%d]' % count, item)

    def __init__(self, value):
        self.val = value
        self.key_type = self.val.type.strip_typedefs().template_argument(0)
        self.value_type = self.val.type.strip_typedefs().template_argument(1)

    def get_pointer(self):
        return self.val["m_flat_tree"]["m_data"]["m_vect"]["members_"]["m_start"]

    def get_size(self):
        return self.val["m_flat_tree"]["m_data"]["m_vect"]["members_"]["m_size"]

    def get_capacity(self):
        return self.val["m_flat_tree"]["m_data"]["m_vect"]["members_"]["m_capacity"]

    def has_elements(self):
        if self.get_pointer():
            return True
        else:
            return False

    def to_string (self):
        if (self.has_elements()):
            return "boost::container::flat_map<%s, %s> with %d elements, capacity %d" % (
                self.key_type, self.value_type, self.get_size(), self.get_capacity())
        else:
            return "empty boost::container::flat_map<%s, %s>" % (
                self.key_type, self.value_type)

    def children (self):
        return self.Iterator(self.get_pointer(), self.get_size())

    def display_hint(self):
        return 'map'

# Iterator used for flat_set/flat_map
@_register_printer
class BoostContainerVectorIterator:
    "Pretty Printer for boost::container::container_detail::vector_iterator (Boost.Container)"
    printer_name = 'boost::container::container_detail::vector_iterator'
    version = '1.52'
    type_name_re = '^boost::container::container_detail::vector.*_iterator<.*>$'

    def __init__(self, value):
        self.val = value

    def to_string(self):
        if self.val["m_ptr"]:
            return self.val["m_ptr"].dereference()
        else:
            return "uninitialized %s" % (self.val.type)

##################################################
# boost::intrusive::set                          #
##################################################

def get_named_template_argument(gdb_type, arg_name):
    n = 0;
    while True:
        try:
            arg = gdb_type.strip_typedefs().template_argument(n)
            if (str(arg).startswith(arg_name)):
                return arg
            n += 1
        except RuntimeError:
            return None

def intrusive_container_has_size_member(intrusive_container_type):
    constant_size_arg = get_named_template_argument(intrusive_container_type, "boost::intrusive::constant_time_size")
    if not constant_size_arg:
        return True
    if str(constant_size_arg.template_argument(0)) == 'false':
        return False
    return True

def intrusive_iterator_to_string(iterator_value):
    opttype = iterator_value.type.template_argument(0).template_argument(0)

    base_hook_traits = get_named_template_argument(opttype, "boost::intrusive::detail::base_hook_traits")
    if base_hook_traits:
        value_type = base_hook_traits.template_argument(0)
        return iterator_value["members_"]["nodeptr_"].cast(value_type.pointer()).dereference()

    member_hook_traits = get_named_template_argument(opttype, "boost::intrusive::detail::member_hook_traits")
    if member_hook_traits:
        value_type = member_hook_traits.template_argument(0)
        member_offset = member_hook_traits.template_argument(2).cast(gdb.lookup_type("size_t"))
        current_element_address = iterator_value["members_"]["nodeptr_"].cast(gdb.lookup_type("size_t")) - member_offset
        return current_element_address.cast(value_type.pointer()).dereference()

    return iterator_value["members_"]["nodeptr_"]

@_register_printer
class BoostIntrusiveSet:
    "Pretty Printer for boost::intrusive::set (Boost.Intrusive)"
    printer_name = 'boost::intrusive::set'
    version = '1.40'
    type_name_re = '^boost::intrusive::set<.*>$'

    class Iterator:
        def __init__(self, rb_tree_header, element_pointer_type, member_offset=0):
            self.header = rb_tree_header
            self.member_offset = member_offset
            if member_offset == 0:
                self.node_type = element_pointer_type
            else:
                self.node_type = gdb.lookup_type("boost::intrusive::rbtree_node<void*>").pointer();
                self.element_pointer_type = element_pointer_type

            if rb_tree_header['parent_']:
                self.node = rb_tree_header['left_'].cast(self.node_type)
            else:
                self.node = 0

            self.count = 0

        def __iter__(self):
            return self

        def get_element_pointer_from_node_pointer(self):
            if self.member_offset == 0:
                return self.node
            else:
                current_element_address = self.node.cast(gdb.lookup_type("size_t")) - self.member_offset
                return current_element_address.cast(self.element_pointer_type)

        def next(self):
            # empty set or reached rightmost leaf
            if not self.node:
                raise StopIteration
            item = self.get_element_pointer_from_node_pointer().dereference()
            if self.node != self.header["right_"].cast(self.node_type):
                # Compute the next node.
                node = self.node
                if node.dereference()['right_']:
                    node = node.dereference()['right_']
                    while node.dereference()['left_']:
                        node = node.dereference()['left_']
                else:
                    parent = node.dereference()['parent_']
                    while node == parent.dereference()['right_']:
                        node = parent
                        parent = parent.dereference()['parent_']
                    if node.dereference()['right_'] != parent:
                        node = parent
                self.node = node.cast(self.node_type)
            else:
                self.node = 0
            result = ('[%d]' % self.count, item)
            self.count = self.count + 1
            return result

    def __init__(self, value):
        self.typename = value.type_name
        self.val = value
        self.element_type = self.val.type.strip_typedefs().template_argument(0)

    def get_header(self):
        return self.val["tree_"]["data_"]["node_plus_pred_"]["header_plus_size_"]["header_"]

    def get_size(self):
        return self.val["tree_"]["data_"]["node_plus_pred_"]["header_plus_size_"]["size_"]

    def has_elements(self):
        header = self.get_header()
        first_element = header["parent_"]
        if first_element:
            return True
        else:
            return False

    def to_string (self):
        if (intrusive_container_has_size_member(self.val.type)):
            return "boost::intrusive::set<%s> with %d elements" % (self.element_type, self.get_size())
        elif (self.has_elements()):
            return "non-empty boost::intrusive::set<%s>" % self.element_type
        else:
            return "empty boost::intrusive::set<%s>" % self.element_type

    def children (self):
        element_pointer_type = self.element_type.pointer()
        member_hook = get_named_template_argument(self.val.type, "boost::intrusive::member_hook")
        if member_hook:
            member_offset = member_hook.template_argument(2).cast(gdb.lookup_type("size_t"))
            return self.Iterator(self.get_header(), element_pointer_type, member_offset)
        else:
            return self.Iterator(self.get_header(), element_pointer_type)


@_register_printer
class BoostIntrusiveTreeIterator:
    "Pretty Printer for boost::intrusive::set<*>::iterator (Boost.Intrusive)"
    printer_name = 'boost::intrusive::tree_iterator'
    version = '1.40'
    type_name_re = '^boost::intrusive::tree_iterator<.*>$'

    def __init__(self, value):
        self.val = value
        self.typename = value.type_name

    def to_string(self):
        return intrusive_iterator_to_string(self.val)


##################################################
# boost::intrusive::list                         #
##################################################

@_register_printer
class BoostIntrusiveList:
    "Pretty Printer for boost::intrusive::list (Boost.Intrusive)"
    printer_name = 'boost::intrusive::list'
    version = '1.40'
    type_name_re = '^boost::intrusive::list<.*>$'

    class Iterator:
        def __init__(self, list_header, element_pointer_type, member_offset=0):
            self.header = list_header

            self.member_offset = member_offset
            if member_offset == 0:
                self.node_type = element_pointer_type
            else:
                self.node_type = gdb.lookup_type("boost::intrusive::list_node<void*>").pointer();
                self.element_pointer_type = element_pointer_type

            next_node = list_header['next_']
            if next_node != list_header.address:
                self.node = next_node.cast(self.node_type)
            else:
                self.node = 0

            self.count = 0

        def __iter__(self):
            return self

        def get_element_pointer_from_node_pointer(self):
            if self.member_offset == 0:
                return self.node
            else:
                current_element_address = self.node.cast(gdb.lookup_type("size_t")) - self.member_offset
                return current_element_address.cast(self.element_pointer_type)

        def next(self):
            # empty list or reached end
            if not self.node:
                raise StopIteration
            item = self.get_element_pointer_from_node_pointer().dereference()
            next_node = self.node['next_']
            if next_node != self.header.address:
                self.node = next_node.cast(self.node_type)
            else:
                self.node = 0
            result = ('[%d]' % self.count, item)
            self.count = self.count + 1
            return result

    def __init__(self, value):
        self.typename = value.type_name
        self.val = value
        self.element_type = self.val.type.strip_typedefs().template_argument(0)

    def get_header(self):
        return self.val["data_"]["root_plus_size_"]["root_"]

    def get_size(self):
        return self.val["data_"]["root_plus_size_"]["size_"]

    def has_elements(self):
        header = self.get_header()
        first_element = header["next_"]
        root_element = header.address
        if first_element != root_element:
            return True
        else:
            return False

    def to_string(self):
        if (intrusive_container_has_size_member(self.val.type)):
            return "boost::intrusive::list<%s> with %d elements" % (self.element_type, self.get_size())
        elif (self.has_elements()):
            return "non-empty boost::intrusive::list<%s>" % self.element_type
        else:
            return "empty boost::intrusive::list<%s>" % self.element_type

    def children(self):
        element_pointer_type = self.element_type.pointer()
        member_hook = get_named_template_argument(self.val.type, "boost::intrusive::member_hook")
        if member_hook:
            member_offset = member_hook.template_argument(2).cast(gdb.lookup_type("size_t"))
            return self.Iterator(self.get_header(), element_pointer_type, member_offset)
        else:
            return self.Iterator(self.get_header(), element_pointer_type)

@_register_printer
class BoostIntrusiveListIterator:
    "Pretty Printer for boost::intrusive::list<*>::iterator (Boost.Intrusive)"
    printer_name = 'boost::intrusive::list_iterator'
    version = '1.40'
    type_name_re = '^boost::intrusive::list_iterator<.*>$'

    def __init__(self, value):
        self.val = value

    def to_string(self):
        return intrusive_iterator_to_string(self.val)

@_register_printer
class BoostGregorianDate:
    "Pretty Printer for boost::gregorian::date"
    printer_name = 'boost::gregorian::date'
    version = '1.40'
    type_name_re = '^boost::gregorian::date$'

    def __init__(self, value):
        self.typename = value.type_name
        self.value = value

    def to_string(self):
        n = int(self.value['days_'])
        # Check for uninitialized case
        if n==2**32-2:
            return '(%s) uninitialized' % self.typename
        # Convert date number to year-month-day
        a = n + 32044
        b = (4*a + 3) / 146097
        c = a - (146097*b)/4
        d = (4*c + 3)/1461
        e = c - (1461*d)/4
        m = (5*e + 2)/153
        day = e + 1 - (153*m + 2)/5
        month = m + 3 - 12*(m/10)
        year = 100*b + d - 4800 + (m/10)
        return '(%s) %4d-%02d-%02d' % (self.typename, year,month,day)

@_register_printer
class BoostPosixTimePTime:
    "Pretty Printer for boost::posix_time::ptime"
    printer_name = 'boost::posix_time::ptime'
    version = '1.40'
    type_name_re = '^boost::posix_time::ptime$'

    def __init__(self, value):
        self.typename = value.type_name
        self.value = value

    def to_string(self):
        n = int(self.value['time_']['time_count_']['value_'])
        # Check for uninitialized case
        if n==2**63-2:
            return '(%s) uninitialized' % self.typename
        # Check for boost::posix_time::pos_infin case
        if n==2**63-1:
            return '(%s) positive infinity' % self.typename
        # Check for boost::posix_time::neg_infin case
        if n==-2**63:
            return '(%s) negative infinity' % self.typename
        # Subtract the unix epoch from the timestamp and convert the resulting timestamp into something human readable
        unix_epoch_time = (n-210866803200000000)/1000000.0
        time_string = datetime.datetime.fromtimestamp(unix_epoch_time).strftime('%Y-%b-%d %H:%M:%S.%f')
        return '(%s) %s' % (self.typename, time_string)

#
# Some utility methods.
#

def _paren_split(s, target_paren = '<'):
    "Split the given string at commas (,) at the first paranthesis sublevel of target_paren, ignoring commas within other paranthesized blocks. This can be used to extract template arguments."
    open_parens = '([{<'
    close_parens = ')]}>'
    end_paren = {}
    end_paren['('] = ')'
    end_paren['['] = ']'
    end_paren['{'] = '}'
    end_paren['<'] = '>'
    if target_paren not in open_parens:
        print >> sys.stderr, 'error: _paren_split: target_paren [' + target_paren + '] must be one of [' + open_parens + ']'
        return None
    paren_stack = []
    res = []
    st = 0
    for i in xrange(len(s)):
        if s[i] in open_parens:
            if len(paren_stack) == 0 and s[i] == target_paren:
                st = i + 1
            paren_stack.append(s[i])
        elif s[i] in close_parens:
            if len(paren_stack) == 0 or s[i] != end_paren[paren_stack[-1]]:
                # mismatched parens
                return None
            if len(paren_stack) == 1 and paren_stack[0] == target_paren:
                res += [[st, i]]
                st = i + 1
            del paren_stack[-1]
        elif s[i] == ',':
            if len(paren_stack) == 0:
                # comma among primary identifiers
                return None
            if len(paren_stack) == 1 and paren_stack[0] == target_paren:
                res += [[st, i]]
                st = i + 1
    return res

def _strip_inheritance_qual(s):
    if s.startswith('public '):
        return s[7:]
    if s.startswith('private '):
        return s[8:]
    if s.startswith('protected '):
        return s[10:]
    return s

def _get_subtype(basic_type, idx):
    "Return the subtype of a given type. idx can be an integer indicating the index of the subtype to be returned, or a list of such indexes, in which case a list of types is returned."
    s = execute(ptype_cmd + ' ' + str(basic_type), True, True)
    if not s.startswith('type = '):
        print >> sys.stderr, 'error: _get_subtype(' + str(basic_type) + '): s = ' + s
        return None
    s = s[7:]
    s = s.split('\n')[0]
    if not s[-1] == '{':
        print >> sys.stderr, 'error: _get_subtype(' + str(basic_type) + '): not a class?'
        return None
    s = s[:-1]
    if len(s.split(' : ')) != 2:
        print >> sys.stderr, 'error: _get_subtype(' + str(basic_type) + '): no subtypes?'
        return None
    s = 'void< ' + s.split(' : ')[1] + ' >'
    r = _paren_split(s)
    if len(r) == 0:
        print >> sys.stderr, 'error: _get_subtype(' + str(basic_type) + '): s = ' + s + '; r = ' + str(r)
        return None
    if type(idx) == list:
        idx_list = idx
    else:
        idx_list = [idx]
    res = []
    for i in idx_list:
        if i >= len(r):
            res.append(None)
        else:
            t_s = _strip_inheritance_qual(s[r[i][0]:r[i][1]].strip())
            t = gdb.lookup_type(t_s)
            res.append(t)
    if type(idx) == list:
        return res
    else:
        return res[0]

def _is_boost_multi_index(v):
    return str(v.basic_type).startswith('boost::multi_index::multi_index_container')

def _boost_multi_index_get_indexes(v):
    "Save the index types of a multi_index_container in v.indexes."
    v.main_args = _paren_split(str(v.basic_type))
    if len(v.main_args) != 3:
        print >> sys.stderr, 'error parsing: ' + str(v.basic_type)
        return False
    arg2_str = str(v.basic_type)[v.main_args[1][0]:v.main_args[1][1]] # the 2nd template arg
    arg2_args = _paren_split(arg2_str)
    if len(arg2_args) == 0:
        print >> sys.stderr, 'error parsing arg2 of: ' + str(v.basic_type)
        return False
    v.indexes = []
    for r in arg2_args:
        v.indexes.append(arg2_str[r[0]:r[1]].split('<')[0].strip())

# The size in pointers of the index fields for all index types.
_boost_multi_index_index_size = {}
_boost_multi_index_index_size['boost::multi_index::ordered_unique'] = 3
_boost_multi_index_index_size['boost::multi_index::ordered_non_unique'] = 3
_boost_multi_index_index_size['boost::multi_index::hashed_unique'] = 1
_boost_multi_index_index_size['boost::multi_index::hashed_non_unique'] = 1
_boost_multi_index_index_size['boost::multi_index::sequenced'] = 2
_boost_multi_index_index_size['boost::multi_index::random_access'] = 1

#
# The following is an experimental printer for boost::multi_index_container
# using ordered unique/nonunique or sequenced index. This might not always
# work for various reasons.
#
# 1. I did not fully decode the templated construction of these containers.
# For further hacks, here are the assumptions made by the current code:
# - Given the address x of a boost::multi_index_container object, one can find
#   the address of the head node by casting the container into its second
#   subclass, and following the 'member' pointer.
# - Each node is stored in memory as:
#   (Element, index_n-1_fields, ..., index_0_fields)
# - The size of an Element is rounded up to the next multiple of 8.
# - The size of the index fields for various indexes are in
#   _boost_multi_index_index_size (in number of pointers).
# - For ordered & sequenced indexes:
# - The i-th index field pointers (3 for ordered, 2 for sequenced) point to the
#   address of the destination node's i-th index fields pointers (not to the
#   address of the destination node's Element).
# - The head node pointer of the multiindex container points to the head node's
#   Element address.
# - For ordered indexes:
#   - The last bit of parent_ptr is used to store the node color in the tree, so
#     it must be AND-ed to 0 before following the ptr.
#   - Inside the head node, the pointers specify:
#     parent_ptr: root node
#     left_ptr: node with smallest element
#     right_ptr: node with largest element
#   - The elements are stored in a sorted binary tree (probably balanced, but we
#     don't care about that for printing). So, given a node x, all nodes in the
#     left subtree of x appear before x when ordered, and all nodes in the right
#     subtree appear after x.
# - For sequenced indexes:
#   - The index field contains: previous@0 and next@1.
#   - To traverse the container, keep following next pointers until returning
#     back to the head node.
#
# 2. The python framework in gdb is limited. To cast a
# boost::multi_index_container to one of its super classes, I use an awkward
# parse_and_eval() that can be broken by as little as output formatting changes.
#

@_conditionally_register_printer(_have_execute_to_string)
class Boost_Multi_Index:
    "Printer for boost::multi_index_container"
    printer_name = 'boost::multi_index_container'
    version = '1.42'

    #
    # To specify which index to use for printing for a specific container
    # (dynamically, inside gdb), add its address here as key, and the desired
    # index as value. E.g.:
    #
    # (gdb) p &s_5
    # $2 = (Int_Set_5 *) 0x7fffffffd770
    # (gdb) python import boost.printers
    # (gdb) python boost.printers.Boost_Multi_Index.idx[0x7fffffffd770] = 1
    # (gdb) p s_5
    #
    idx = {}

    #
    # Not supported indexes (hashes and random-access) are captured and printed
    # by this subprinter. To disable this, set this to False. This can be set in
    # the source code, in .gdbinit where the printers are loaded, or dynamically
    # from inside gdb.
    #
    print_not_supported = True

    @classmethod
    def supports(self_type, v):
        if not _is_boost_multi_index(v):
            return False
        _boost_multi_index_get_indexes(v)
        if v.idx >= len(v.indexes):
            return False
        return (self_type.print_not_supported
                or v.indexes[v.idx] == 'boost::multi_index::ordered_unique'
                or v.indexes[v.idx] == 'boost::multi_index::ordered_non_unique'
                or v.indexes[v.idx] == 'boost::multi_index::sequenced')

    @staticmethod
    def get_val_ptr(node_ptr, index_offset):
        return node_ptr - index_offset

    def __init__(self, v):
        # clear up the type_name:
        # pick template name
        self.type_name = v.type_name[0:v.main_args[0][0]].strip()[:-1]
        # add 2 args only (omit allocator)
        self.type_name += ('<'
                           + v.type_name[v.main_args[0][0]:v.main_args[0][1]].strip()
                           + ', '
                           + v.type_name[v.main_args[1][0]:v.main_args[1][1]].strip()
                           + '>')
        # remove bulk
        self.type_name = ''.join(self.type_name.split('boost::multi_index::detail::'))
        self.type_name = ''.join(self.type_name.split('boost::multi_index::'))
        self.type_name = ''.join(self.type_name.split('boost::detail::'))
        self.type_name = ''.join(self.type_name.split(', mpl_::na'))
        self.type_name = ''.join(self.type_name.split('mpl_::na'))
        self.type_name = ''.join(self.type_name.split('tag<>'))
        self.type_name = '<>'.join(self.type_name.split('< >'))
        self.type_name = 'boost::' + self.type_name
        # add index specifier
        self.type_name += '[idx=' + str(v.idx) + ']'
        #print >> sys.stderr, 'type_name: ' + self.type_name

        # index type
        self.index_type = v.indexes[v.idx]

        # node count
        self.node_count = long(v['node_count'])

        # first, we need the element type
        self.elem_type = v.basic_type.template_argument(0)
        #print >> sys.stderr, 'elem_type: ' + str(self.elem_type)

        # next, we compute the element size and round it up to the pointer size
        ptr_size = gdb.lookup_type('void').pointer().sizeof
        self.elem_size = ((self.elem_type.sizeof - 1) / ptr_size + 1) * ptr_size
        #print >> sys.stderr, 'elem_size: ' + str(self.elem_size)

        # next, we cast the object into its 2nd subtype which should be header_holder
        # and retrieve the head node
        header_holder_subtype = _get_subtype(v.basic_type, 1)
        if header_holder_subtype == None:
            print >> sys.stderr, 'error computing 2nd subtype of ' + str(v.basic_type)
            return None
        if not str(header_holder_subtype).strip().startswith('boost::multi_index::detail::header_holder'):
            print >> sys.stderr, '2nd subtype of multi_index_container is not header_holder'
            return None
        head_node = v.cast(header_holder_subtype)['member'].dereference()
        #print >> sys.stderr, 'head_node.type.sizeof: ' + str(head_node.type.sizeof)

        # finally, we compute the offset from the element address
        # to the index field address, as well as the address of the parent_ptr
        # inside the head node
        # to do that, we compute the size of all indexes prior to the current one
        self.index_offset = head_node.type.sizeof
        for i in xrange(v.idx + 1):
            self.index_offset -= _boost_multi_index_index_size[v.indexes[i]] * ptr_size
        #print >> sys.stderr, 'index_offset: ' +  str(self.index_offset)

        self.head_index_ptr = long(head_node.address) + self.index_offset
        #print >> sys.stderr, 'head_index_ptr: ' + hex(self.head_index_ptr)

    def empty_cont(self):
        return self.node_count == 0

    class empty_iterator:
        def __init__(self):
            pass
        def __iter__(self):
            return self
        def next(self):
            raise StopIteration

    class na_iterator:
        def __init__(self, index_type):
            self.saw_msg = False
            self.index_type = index_type
        def __iter__(self):
            return self
        def next(self):
            if not self.saw_msg:
                self.saw_msg = True
                return (self.index_type, 'printer not implemented')
            raise StopIteration

    class ordered_iterator:
        @staticmethod
        def get_parent_ptr(node_ptr):
            return long(str(parse_and_eval('*((void**)' + str(node_ptr) + ')')), 16) & (~1L)

        @staticmethod
        def get_left_ptr(node_ptr):
            return long(str(parse_and_eval('*((void**)' + str(node_ptr) + ' + 1)')), 16)

        @staticmethod
        def get_right_ptr(node_ptr):
            return long(str(parse_and_eval('*((void**)' + str(node_ptr) + ' + 2)')), 16)

        def __init__(self, elem_type, index_offset, first, last):
            self.elem_type = elem_type
            self.index_offset = index_offset
            self.crt = first
            self.last = last
            self.saw_last = False
            self.count = 0

        def __iter__(self):
            return self

        def next(self):
            if self.crt == self.last and self.saw_last:
                raise StopIteration
            crt = self.crt
            #print >> sys.stderr, 'crt: ' + hex(crt)
            if self.crt == self.last:
                self.saw_last = True
            else:
                if self.get_right_ptr(self.crt) != 0:
                    # next is leftmost node in right subtree
                    #print >> sys.stderr, 'next is in right subtree'
                    self.crt = self.get_right_ptr(self.crt)
                    while self.get_left_ptr(self.crt) != 0:
                        self.crt = self.get_left_ptr(self.crt)
                else:
                    # next is first ancestor from which crt is in left subtree
                    #print >> sys.stderr, 'next is an ancestor'
                    while True:
                        old_crt = self.crt
                        self.crt = self.get_parent_ptr(self.crt)
                        if self.get_left_ptr(self.crt) == old_crt:
                            break
                #print >> sys.stderr, 'next: ' + hex(self.crt)
            count = self.count
            self.count = self.count + 1
            val_ptr = Boost_Multi_Index.get_val_ptr(crt, self.index_offset)
            return ('[%s]' % hex(int(val_ptr)),
                    str(parse_and_eval('*(' + str(self.elem_type) + '*)'
                                       + str(val_ptr))))

    class sequenced_iterator:
        @staticmethod
        def get_prev_ptr(node_ptr):
            return long(str(parse_and_eval('*((void**)' + str(node_ptr) + ')')), 16)

        @staticmethod
        def get_next_ptr(node_ptr):
            return long(str(parse_and_eval('*((void**)' + str(node_ptr) + ' + 1)')), 16)

        def __init__(self, elem_type, index_offset, begin, end):
            self.elem_type = elem_type
            self.index_offset = index_offset
            self.crt = begin
            self.end = end
            self.count = 0

        def __iter__(self):
            return self

        def next(self):
            if self.crt == self.end:
                raise StopIteration
            crt = self.crt
            self.crt = self.get_next_ptr(self.crt)
            count = self.count
            self.count = self.count + 1
            val_ptr = Boost_Multi_Index.get_val_ptr(crt, self.index_offset)
            return ('[%s]' % hex(int(val_ptr)),
                    str(parse_and_eval('*(' + str(self.elem_type) + '*)'
                                       + str(val_ptr))))

    def children(self):
        if self.empty_cont():
            return self.empty_iterator()
        if (self.index_type == 'boost::multi_index::ordered_unique'
            or self.index_type == 'boost::multi_index::ordered_non_unique'):
            return self.ordered_iterator(
                self.elem_type,
                self.index_offset,
                self.ordered_iterator.get_left_ptr(self.head_index_ptr),
                self.ordered_iterator.get_right_ptr(self.head_index_ptr))
        elif self.index_type == 'boost::multi_index::sequenced':
            return self.sequenced_iterator(
                self.elem_type,
                self.index_offset,
                self.sequenced_iterator.get_next_ptr(self.head_index_ptr),
                self.head_index_ptr)
        return self.na_iterator(self.index_type)

    def to_string(self):
        if self.empty_cont():
            return 'empty %s' % self.type_name
        return '%s' % self.type_name
